#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 498. 对角线遍历
中等
408
相关企业
给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。*
 * */

//这个是一个正方形 这样写不行的
vector<int> findDiagonalOrder1(vector<vector<int>> &mat) {

    vector<int> ret;

    ret.push_back(mat[0][0]);

    for (int i = 1; i < mat[0].size(); i++) {
        int row = 0;
        int col = i;
        vector<int> temp;
        while (col >= 0 && row < mat.size()) {
            if (mat[row][col] == INT_MAX)
                break;

            temp.push_back(mat[row][col]);

            mat[row][col] = INT_MAX;

            row++;
            col--;
        }

        if (i % 2 == 0) {
            reverse(temp.begin(), temp.end());
        }

        ret.insert(ret.end(), temp.begin(), temp.end());
    }


    // 21  12
    for (int i = 1; i < mat[0].size(); i++) {
        int row = mat.size() - 1;
        int col = i;
        vector<int> temp;
        while (col <= mat[0].size() - 1 && row >= 0) {
            if (mat[row][col] == INT_MAX)
                break;
            temp.push_back(mat[row][col]);

            mat[row][col] = INT_MAX;


            row--;
            col++;
        }

        if (i % 2 != 0) {
            reverse(temp.begin(), temp.end());
        }

        ret.insert(ret.end(), temp.begin(), temp.end());
    }


    return ret;
}


vector<int> findDiagonalOrder(vector<vector<int>> &mat) {
    vector<int> ret;
    if (mat == nullptr || mat.size() == 0)
        return ret;


    int row = mat.size(), col = mat[0].size();
    int r = 0, c = 0;
    int size = row * col;
    ret.resize(size);
    for (int i = 0; i < size; ++i) {
        ret[i] = mat[r][c];
        // r + c 即为遍历的层数，偶数向上遍历，奇数向下遍历
        if ((r + c) % 2 == 0) {
            if (c == col - 1) {
                //向下移动
                r++;
            } else if (r == 0) {
                /// 往右边移动 这个必须得在上面那个下面
                c++;
            } else {
                r--;
                c++;
                //向上移动
            }

        } else {
            //说明这个是向下走的
            if (r == row - 1) {
                c++;//列++
            } else if (c == 0) {
                //列为0 说明应该向上走了
                r--;
            } else {
                //否则就是向下走了斜着
                r++;
                c--;
            }


        }


    }


    return ret;


}